Cây (Tree) là một cấu trúc dữ liệu phân cấp phi tuyến tính, mô phỏng các kiến trúc tổ chức trong thế giới thực (như hệ thống tệp hoặc dòng họ). Khác với cách sắp xếp tuyến tính của danh sách, ngăn xếp và hàng đợi, bản chất của cây nằm ở tính chấtphân cấp (Hierarchical)vàđệ quy (Recursive).
1. Phân tích hình dạng cây
- đỉnh (Node): Đơn vị cơ bản chứa khóa (Key) và dữ liệu tải.
- đỉnh gốc (Root): Đỉnh duy nhất không có cạnh đi vào, là điểm khởi đầu của cây.
- cạnh (Edge): Đường đi duy nhất kết nối các đỉnh, đại diện cho mối quan hệ cha-con.
- đỉnh lá (Leaf): Đỉnh cuối cùng không có con, là ranh giới tự nhiên để kết thúc đệ quy.
2. Hai góc nhìn định nghĩa đệ quy
Chúng ta có thể hiểu cây từ hai góc nhìn sau:
Góc nhìn đồ họa
Là đồ thị liên thông, không chu trình, được tạo thành từ các đỉnh và cạnh, mỗi đỉnh (trừ đỉnh gốc) có đúng một cha.
Là đồ thị liên thông, không chu trình, được tạo thành từ các đỉnh và cạnh, mỗi đỉnh (trừ đỉnh gốc) có đúng một cha.
Góc nhìn đệ quy
Một cây sẽ rỗng hoặc gồm một đỉnh gốc và một hoặc nhiều cây con (Subtree).
Một cây sẽ rỗng hoặc gồm một đỉnh gốc và một hoặc nhiều cây con (Subtree).
Ví dụ về cây DOM HTML
Trong HTML,
<html> là đỉnh gốc,<body> và <head> là các đỉnh anh em. Mỗi thẻ cùng nội dung lồng ghép của nó tạo thành một cây con. Cấu trúc này cho phép chúng ta di chuyển toàn bộ <ul> cùng tất cả các <li> mà không làm hỏng thứ tự phân cấp bên trong.